package BestTimetoBuyandSellStockIII;

public class Solution {
    public int maxProfit(int[] prices) {
    	if (prices.length==0) return 0;
        int[][] f=new int[prices.length+1][4];
        f[0][0]=-prices[0];
        int first=Integer.MIN_VALUE;
        int result=0;
        for (int i=1;i<prices.length;i++){
        	f[i][0]=Math.max(f[i-1][0], -prices[i]);
        	f[i][1]=Math.max(f[i-1][0]+prices[i], f[i-1][1]-prices[i-1]+prices[i]);
        	if (f[i][1]>first) first=f[i][1];
        	if (i>=2){
        		f[i][2]=first-prices[i]; 
        	}
        	if (i>=3){
        		f[i][3]=Math.max(f[i-1][2]+prices[i], f[i-1][3]-prices[i-1]+prices[i]);
        	}
        	result=Math.max(result,f[i][3]);
        	result=Math.max(result,f[i][1]);
        }
        return result;
    }
    public static void main(String args[]) {
    	int[] t={1,4,2,7};
    	Solution so=new Solution();
    	System.out.println(so.maxProfit(t));
		
	}
}
